#include <iostream>
#include <vector>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

template <class K,class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

template<class K>
struct _hash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct _hash<string>
{
	size_t operator()(const string& key)
	{
		size_t hashi = 0;
		for (auto e : key)
		{
			hashi += e;
			hashi *= 131;
		}
		return hashi;
	}
};

template <class K,class V,class hash = _hash<K>>
class HashTable
{
public:
	typedef HashData<K, V> Data;

	HashTable(size_t size = 10)
	{
		_table.resize(size);
		_n = 0;
	}

	Data* Find(const K& key)
	{
		hash hs;
		size_t hashi = hs(key) % _table.size();
		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._kv.first == key && _table[hashi]._state==EXIST)
				return &_table[hashi];
			hashi++;
			hashi %= _table.size();
		}
		return nullptr;
	}

	bool Insert(const pair<K, V> kv)
	{
		if (Find(kv.first))
			return false;

		if (_n / (double)_table.size() >= 0.7)
		{
			size_t newsize = _table.size() * 2;
			HashTable<K, V, hash> newtable(newsize);
			for (auto& e : _table)
			{
				if (e._state == EXIST)
					newtable.Insert(e._kv);
			}
			_table.swap(newtable._table);
		}

		hash hs;
		size_t hashi = hs(kv.first)%_table.size();
		while (_table[hashi]._state == EXIST)
		{
			++hashi;
			hashi%=_table.size();
		}

		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;
		return true;
	}

	bool Erase(const K& key)
	{
		Data* ptr = Find(key);
		if (ptr)
		{
			ptr->_state = DELETE;
			--_n;
			return true;
		}
		return false;
	}

private:
	vector<Data> _table;
	size_t _n = 0;
};

int main()
{
	HashTable<int, int> h;
	h.Insert(make_pair(1,1));
	h.Insert(make_pair(6,6));
	h.Insert(make_pair(4,4));
	h.Insert(make_pair(3,3));
	h.Insert(make_pair(2, 2));
	h.Insert(make_pair(22, 22));
	h.Insert(make_pair(23, 23));
	h.Erase(2);
	h.Insert(make_pair(42, 42));
	h.Insert(make_pair(2, 2));
	h.Insert(make_pair(2, 2));

	return 0;
}